Step 1: Building the Graph

First, we must read the input and store the network in our Adjacency List.

Guidance for Step 1

  • Read `V` and `E`: Get the number of vertices and edges.
  • Initialize `graph`: Create a list of `V` empty lists. `graph[i]` will store the neighbors of node `i`.
  • Loop `E` times: Read each `u`, `v`, and `w`.
  • Bi-directional: This is key! If `u` connects to `v` with weight `w`, you must add `(v, w)` to `graph[u]` AND add `(u, w)` to `graph[v]`. 
# 1. Read V and E
V_str, E_str = input().split()
V = int(V_str)
E = int(E_str)

# 2. Initialize the adjacency list
graph = [ [] for _ in range(______) ]

# 3. Loop E times
for _ in range(______):
    u_str, v_str, w_str = input().split()
    u = int(u_str)
    v = int(v_str)
    w = int(w_str)
    
    # 4. Add bi-directional edges
    # Store as a tuple: (neighbor, weight)
    graph[______].append( (______, ______) )
    graph[______].append( (______, ______) )

# Finally, read the source node
S = int(input())
Copied!